/*
82. 最大矩形
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

先看一个问题:
84. 柱状图中最大的矩形
给定一个一维数组，每个值表示直方图高度，求构成最大矩形面积
arr = [4,3,2,5,6]:  结果为10

  4 3 2 5 6
|         *
|       * *
| *     * *
| * *   * *
| * * * * *
| * * * * *
------------
[4,3,2,5,6]

思路: 单调栈(栈顶大->小), 遍历数组i，
入栈时不满足单调条件，弹栈位置j，如果栈为空,说明该j位置数值对应的"柱子"可以移动到最左边, 否则就是新的栈顶位置
同时向右移动能移动的位置就是i，area = arr[j]*移动距离

遍历完成后清算栈，弹出位置j，可以移动到右边界，栈不空，此时栈顶为k, 则j左边界为k,
若栈为空，则j可以移动到最左边
 */

/**
 * 一维数组直方图求解
 * @param {number[]} arr
 * @return number
 */
function getMaxRectangleFromBottom (arr) {
  let maxArea = 0
  const monoStack = []
  for (let i = 0, n = arr.length; i < n; i++) {
    while (monoStack.length && arr[monoStack[monoStack.length - 1]] >= arr[i]) {
      const position = monoStack.pop()
      const rightEdge = i
      const leftEdge = monoStack.length === 0 ? -1 : monoStack[monoStack.length - 1]
      const curArea = arr[position] * (rightEdge - leftEdge - 1)
      maxArea = Math.max(maxArea, curArea)
    }
    monoStack.push(i)
  }
  while (monoStack.length) {
    const position = monoStack.pop()
    const rightEdge = arr.length
    const leftEdge = monoStack.length === 0 ? -1 : monoStack[monoStack.length - 1]
    const curArea = arr[position] * (rightEdge - leftEdge - 1)
    maxArea = Math.max(maxArea, curArea)
  }
  return maxArea
}

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function (matrix) {
  let maxArea = 0
  for (let i = 0, n = matrix.length; i < n; i++) {
    if (i === 0) {
      maxArea = getMaxRectangleFromBottom(matrix[i].map(value => parseInt(value)))
    } else {
      const heightArr = new Array(matrix[0].length)
      for (let j = 0, m = heightArr.length; j < m; j++) {
        if (matrix[i][j] === '0') {
          heightArr[j] = 0
        } else {
          heightArr[j] = 1
          let row = i - 1
          while (row >= 0 && matrix[row--][j] === '1') {
            heightArr[j]++
          }
        }
      }
      maxArea = Math.max(maxArea, getMaxRectangleFromBottom(heightArr))
    }
  }
  return maxArea
}

const arr = [
  ['1', '0', '1', '0', '0'],
  ['1', '0', '1', '1', '1'],
  ['1', '1', '1', '1', '1'],
  ['1', '0', '0', '1', '0']
]

console.log(maximalRectangle(arr))
